# include <bits/stdc++.h>
# define MAXN 1000023
using namespace std;

char buf[1 << 18], *fs, *ft;
char ops[1 << 18], *opt = ops, *const opt_end = ops + (1 << 18);
 
inline char getc() { 
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
 
inline int gn() { 
    int k = 0, f = 1;
    char c = getc();
    for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k * f;
}
 
inline void out() { 
    fwrite(ops, 1, opt - ops, stdout);
    opt = ops;
}
 
inline void out(int x, char c) { 
    static char *p = new char[21]();
    *(++p) = c;
    do { 
        *(++p) = x % 10 | 0x30;
        x /= 10;
    } while(x);
    while(*p) { 
        *(opt++) = *(p--);
        if(opt == opt_end) out();
    }
}

inline void out(char c) { 
    *(opt++) = c;
    if(opt == opt_end) out();
}

int s[MAXN][20], n, m;

inline void init() { 
    n = gn() + 1;
    for(int i = 1; i <= n; i++) { 
        s[i][0] = gn();
    }
    for(int j = 1; (1 << j) <= n; j++) { 
        for(int i = 1; i + (1 << j) <= n; i++) { 
            s[i][j] = max(s[i][j - 1], s[i + (1 << (j - 1))][j - 1]);
        }
    }
}

inline int query(int l, int r) {
    int len = r - l + 1;
    int k = 0; 
    while(1 << (k + 1) < len) k++;
    return max(s[l][k], s[r - (1 << k) + 1][k]);
}

inline void solve() {
    m = gn();
    for(int i = 1; i <= m; i++) {
        int l = gn() + 1, r = gn() + 1;
        out(query(l, r), '\n');
    }
}

int main() { 
    freopen("climb.in", "r", stdin);
    freopen("climb.out", "w", stdout);
    init();
    solve();
    out();
}
